package com.zjsru.plan2025.oneday;

import java.util.Arrays;

/**
 * 2275. 按位与结果大于零的最长组合
 *
 * @Author: cookLee
 * @Date: 2025-01-12
 */
public class LargestCombination {

    /**
     * 主
     * \
     * 输入：candidates = [16,17,71,62,12,24,14]
     * 输出：4
     * 解释：组合 [16,17,62,24] 的按位与结果是 16 & 17 & 62 & 24 = 16 > 0 。
     * 组合长度是 4 。
     * 可以证明不存在按位与结果大于 0 且长度大于 4 的组合。
     * 注意，符合长度最大的组合可能不止一种。
     * 例如，组合 [62,12,24,14] 的按位与结果是 62 & 12 & 24 & 14 = 8 > 0 。
     * \
     * 输入：candidates = [8,8]
     * 输出：2
     * 解释：最长组合是 [8,8] ，按位与结果 8 & 8 = 8 > 0 。
     * 组合长度是 2 ，所以返回 2 。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        LargestCombination largestCombination = new LargestCombination();
        int[] candidates = new int[]{16, 17, 71, 62, 12, 24, 14};
        System.out.println(largestCombination.largestCombination2(candidates));
    }

    public int largestCombination(int[] candidates) {
        //题意最大到24位
        int[] count = new int[24];
        for (int candidate : candidates) {
            //计算位数为1的次数
            while (candidate > 0) {
                //该方法返回最低位(即，最右或最低有效“1”位)之后的零(0)位总数
                count[Integer.numberOfTrailingZeros(candidate)]++;
                //其最低位的1置为0
                candidate = candidate & (candidate - 1);
            }
        }
        return Arrays.stream(count).max().getAsInt();
    }

    public int largestCombination2(int[] candidates) {
        int ans = 0;
        for (int i = 0; i < 24; i++) {
            ans = Math.max(ans, this.helper(candidates, i));
        }
        return ans;
    }

    /**
     * 表示 candidates 中从低到高第 i 位为 1 的元素数量
     *
     * @param candidates 候选人
     * @param i          我
     * @return int
     */
    private int helper(int[] candidates, int i) {
        int count = 0;
        for (int candidate : candidates) {
            if ((candidate & (1 << i)) != 0) {
                count++;
            }
        }
        return count;
    }
}
